package com.dragon.datastructure.tree.heap;

import java.util.ArrayList;
import java.util.List;

/**
 * 最大堆
 * 最大堆需要满足 完全二叉树 + 对于每一个节点都有 每一个节点都必须要大于等于 它的 直接子节点
 *
 * @author dragon
 * @since 2019/12/31
 */
public class MaxHeap<E extends Comparable<E>> {

    private List<E> data;


    public MaxHeap(int capacity) {
        data = new ArrayList<>(capacity);
    }

    public MaxHeap() {
        data = new ArrayList<>();
    }

    public MaxHeap(E[] array) {
        data = new ArrayList<>();
        if (array != null) {
            for (E e : array) {
                data.add(e);
            }
        }
        for (int i = parent(data.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.size();
    }

    public boolean isEmpty() {
        return data.size() == 0;
    }

    /**
     * 通过该节点的index找到父节点的index
     *
     * @param index
     * @return
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 没有父节点");
        }

        return (index - 1) / 2;
    }

    /**
     * 通过节点的 index 找到 该节点的 左子节点的 index
     *
     * @param index
     * @return
     */
    private int leftChild(int index) {

        return 2 * index + 1;
    }

    /**
     * 通过节点的 index 找到 该节点的 右子节点的 index
     *
     * @param index
     * @return
     */
    private int rightChild(int index) {

        return 2 * index + 2;
    }

    /**
     * 添加元素
     *
     * @param e
     */
    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    /**
     * 上浮操作，需要比较该j 节点与 父节点的大小，如果大于父节点则与父节点交换位置
     * 循环终止的条件是 j <= 0 或者是 该节点 就小于或者等于 父节点
     *
     * @param j
     */
    private void siftUp(int j) {
        while (j > 0 && data.get(j).compareTo(data.get(parent(j))) > 0) {
            data.set(parent(j), data.set(j, data.get(parent(j))));
            j = parent(j);
        }
    }

    /**
     * 查询出堆中最大的值
     *
     * @return
     */
    public E findMax() {
        if (data.size() == 0) {
            throw new IllegalArgumentException("堆为空,找不到最大的元素");
        }
        return data.get(0);
    }

    /**
     * 取出最大的元素
     *
     * @return
     */
    public E extractMax() {
        E ret = findMax();
        data.set(0, data.get(data.size() - 1));
        data.remove(data.size() - 1);

        siftDown(0);

        return ret;
    }

    /**
     * 下沉操作
     *
     * @param index
     */
    private void siftDown(int index) {
        while (leftChild(index) < data.size()) {
            int j = leftChild(index);
            // 如果该节点的右子节点不为空，并且该节点的左子节点是小于右子节点的
            if ((j + 1) < data.size() && data.get(j).compareTo(data.get(j + 1)) < 0) {
                j++;
            }

            if (data.get(j).compareTo(data.get(index)) <= 0) {
                return;
            }

            data.set(index, data.set(j, data.get(index)));

            index = j;
        }

    }

    /**
     * 取出堆中的最大的元素，并且替换成元素e
     *
     * @param e
     * @return
     */
    public E replace(E e) {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);

        return ret;
    }
}
